package algorithm.middle;

import pojo.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle 173. 二叉搜索树迭代器
 * @Author: 江岸
 * @CreateTime: 2021-03-28 18:23
 * @Description: 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
 * <p>
 * BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
 * boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 * int next()将指针向右移动，然后返回指针处的数字。
 * <p>
 * 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
 * <p>
 * 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-search-tree-iterator
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BSTIterator173 {
    List<TreeNode> list;
    int index = 0;

    public BSTIterator173(TreeNode root) {
        list = new ArrayList<>();
        fun(root);
    }

    public int next() {
        return list.get(index++).val;
    }

    public boolean hasNext() {
        if (index < list.size()) return true;
        return false;
    }

    public void fun(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            fun(root.left);
        }
        list.add(root);
        if (root.right != null) {
            fun(root.right);
        }
    }


    /**
     * 所以，设计迭代器的时候，应避免提前把所有的值都遍历出来；最好能设计成遍历过程中求 next 节点。那就需要用迭代方法了。
     *
     *     把递归转成迭代，基本想法就是用栈。
     *     迭代总体思路是：栈中只保留左节点。
     *
     * 思路必须从递归的访问顺序说起：中序遍历的访问顺序是 左子树 -> 根节点 -> 右子树 的顺序，并且对 左子树 和 右子树 也进行递归。
     *
     * 结合下图，实际访问节点的顺序是：
     *
     *     从 根节点12 开始一路到底遍历到所有左节点，路径保存到栈中；此时栈为 [12, 6, 5]。
     *     弹出栈顶节点，即 叶子节点5 ；
     *     下一个栈顶元素是 该叶子节点 的 根节点6；
     *     然后把 该新的根节点的右子树9 一路到底遍历其所有左节点；栈为 [12, 9, 8, 7]。
     *     继续运行下去，直到栈为空。
     *
     * 根据上面的遍历顺序，我们得出迭代的思路：
     *
     *     构造方法：一路到底，把根节点和它的所有左节点放到栈中；
     *     调用 next() 方法：弹出栈顶的节点；
     *         如果它有右子树，则对右子树一路到底，把它和它的所有左节点放到栈中。
     *
     * 链接：https://leetcode-cn.com/problems/binary-search-tree-iterator/solution/fu-xue-ming-zhu-dan-diao-zhan-die-dai-la-dkrm/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    Deque<TreeNode> stack = new LinkedList<TreeNode>();

    public BSTIterator173(TreeNode root, int i) {
        TreeNode node = root;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public int next2() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            TreeNode p = node.right;
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
        }
        return node.val;
    }

    public boolean hasNext2() {
        return !stack.isEmpty();
    }
}
